{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Original Array From Doubled Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findOriginalArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从双倍数组中还原原数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个整数数组&nbsp;<code>original</code>&nbsp;可以转变成一个 <strong>双倍</strong>&nbsp;数组&nbsp;<code>changed</code>&nbsp;，转变方式为将 <code>original</code>&nbsp;中每个元素 <strong>值乘以 2 </strong>加入数组中，然后将所有元素 <strong>随机打乱</strong>&nbsp;。</p>\n",
    "\n",
    "<p>给你一个数组&nbsp;<code>changed</code>&nbsp;，如果&nbsp;<code>change</code>&nbsp;是&nbsp;<strong>双倍</strong>&nbsp;数组，那么请你返回&nbsp;<code>original</code>数组，否则请返回空数组。<code>original</code>&nbsp;的元素可以以&nbsp;<strong>任意</strong>&nbsp;顺序返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>changed = [1,3,4,2,6,8]\n",
    "<b>输出：</b>[1,3,4]\n",
    "<b>解释：</b>一个可能的 original 数组为 [1,3,4] :\n",
    "- 将 1 乘以 2 ，得到 1 * 2 = 2 。\n",
    "- 将 3 乘以 2 ，得到 3 * 2 = 6 。\n",
    "- 将 4 乘以 2 ，得到 4 * 2 = 8 。\n",
    "其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>changed = [6,3,0,1]\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>changed 不是一个双倍数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>changed = [1]\n",
    "<b>输出：</b>[]\n",
    "<b>解释：</b>changed 不是一个双倍数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= changed.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= changed[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-original-array-from-doubled-array](https://leetcode.cn/problems/find-original-array-from-doubled-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-original-array-from-doubled-array](https://leetcode.cn/problems/find-original-array-from-doubled-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,2,6,8]', '[6,3,0,1]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        len_nums=len(changed)\n",
    "        if len_nums%2==1:return []\n",
    "        arr=[]\n",
    "        changed.sort()\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<len_nums:\n",
    "            if arr==[]:arr.append(changed[i])\n",
    "            elif arr[0]*2==changed[i]:\n",
    "                changed[j]=arr[0]\n",
    "                arr=arr[1:]#or arr.pop(0)\n",
    "                j+=1\n",
    "            else:\n",
    "                arr.append(changed[i])\n",
    "            i+=1\n",
    "        if arr != []:return []\n",
    "        return changed[:j]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) & 1 == 1:\n",
    "            return []\n",
    "        changed.sort()\n",
    "        ans = []\n",
    "        i = j = 0\n",
    "        n = len(changed)\n",
    "        while True:\n",
    "            while i < n and changed[i] == -1:\n",
    "                i += 1\n",
    "                if i == n:\n",
    "                    return ans\n",
    "            while (j < n and changed[j] != changed[i] * 2) or j == i:\n",
    "                j += 1\n",
    "            if j < n:\n",
    "                ans.append(changed[i])\n",
    "                changed[i] = -1\n",
    "                changed[j] = -1\n",
    "                j += 1\n",
    "            else:\n",
    "                return []\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) <= 1 or len(changed) & 1 == 1:\n",
    "            return []\n",
    "\n",
    "\n",
    "        changed.sort()\n",
    "\n",
    "        info1 = []\n",
    "        info2 = []\n",
    "\n",
    "        i = 0\n",
    "        # j = -1\n",
    "        info1.append(changed[0])\n",
    "        for t in range(1, len(changed)):\n",
    "            if i < len(info1) and changed[t] == (info1[i] << 1):\n",
    "                info2.append(changed[t])\n",
    "                i += 1\n",
    "            else:\n",
    "                info1.append(changed[t])\n",
    "        \n",
    "        return info1 if len(info1) == len(info2) else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        len_nums=len(changed)\n",
    "        if len_nums%2==1:return []\n",
    "        arr=[]\n",
    "        changed.sort()\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<len_nums:\n",
    "            #if arr==[]:arr.append(changed[i])\n",
    "            if arr!=[] and arr[0]*2==changed[i]:\n",
    "                changed[j]=arr[0]\n",
    "                arr=arr[1:]#or arr.pop(0)\n",
    "                j+=1\n",
    "            else:\n",
    "                arr.append(changed[i])\n",
    "            i+=1\n",
    "        if arr != []:return []\n",
    "        return changed[:j]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        l_changed = len(changed)\n",
    "        if l_changed % 2 == 1:\n",
    "            return []\n",
    "        counter = {}\n",
    "        for num in changed:\n",
    "            if num not in counter:\n",
    "                counter[num] = 1\n",
    "            else:\n",
    "                counter[num] += 1\n",
    "        nums = sorted(counter.keys(), reverse=True)\n",
    "        res = []\n",
    "        for num in nums:\n",
    "            while counter[num] > 0:\n",
    "                if num % 2 != 0:\n",
    "                    return []\n",
    "                else:\n",
    "                    if num // 2 in counter and counter[num // 2] > 0:\n",
    "                        counter[num] -= 1\n",
    "                        counter[num // 2] -= 1\n",
    "                        res.append(num // 2)\n",
    "                    else:\n",
    "                        return []\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed)%2 != 0:\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        tempDoubleVal = []\n",
    "        changed.sort()\n",
    "        \n",
    "        for i in changed:\n",
    "            if tempDoubleVal == []:\n",
    "                res.append(i)\n",
    "                tempDoubleVal.append(i*2)\n",
    "            elif i > tempDoubleVal[0]:  # 最小的值仍然大于最小待匹配的2倍数\n",
    "                return []\n",
    "            elif i == tempDoubleVal[0]:  # 匹配成功\n",
    "                tempDoubleVal = tempDoubleVal[1:]\n",
    "                #tempDoubleVal.pop(0)\n",
    "            else:\n",
    "                res.append(i)\n",
    "                tempDoubleVal.append(i*2)\n",
    "\n",
    "        if tempDoubleVal != []:\n",
    "            return []\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort()\n",
    "        hq = [];\n",
    "        j=0;\n",
    "        for i in range(len(changed)):\n",
    "            if hq and hq[0] * 2 == changed[i]: \n",
    "                changed[j] = heapq.heappop(hq)\n",
    "                j+=1\n",
    "            else: heapq.heappush(hq, changed[i]) \n",
    "        return changed[:j] if not hq else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort()\n",
    "        hq = [];\n",
    "        j=0;\n",
    "        for i in range(len(changed)):\n",
    "            if hq and hq[0] * 2 == changed[i]: \n",
    "                changed[j] = heapq.heappop(hq)\n",
    "                j+=1\n",
    "            else: heapq.heappush(hq, changed[i]) \n",
    "        return changed[:j] if not hq else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n=len(changed) #获得数组的长度\n",
    "        changed.sort() #对数组进行排序\n",
    "        #如果数组长度为奇数，则返回空\n",
    "        if n%2==1:\n",
    "            return []\n",
    "        #建立一个counter\n",
    "        counter=collections.Counter(changed)\n",
    "\n",
    "        res=[]\n",
    "        #左右指针的位置\n",
    "        left=0\n",
    "        right=n-1\n",
    "        #左指针向右，而右指针向左\n",
    "        while left<right:\n",
    "            temp=changed[left]\n",
    "            #如果左边的数字和其两倍数依然在数组中\n",
    "            if counter[temp]>=1 and counter[2*temp]>=1:\n",
    "                res.append(temp)\n",
    "                counter[temp]-=1\n",
    "                counter[2*temp]-=1\n",
    "            #左数字依然在，而两倍数不在\n",
    "            elif counter[temp]>=1 and counter[2*temp]<1:\n",
    "                return []\n",
    "            #左指针右移\n",
    "            left+=1\n",
    "\n",
    "            temp=changed[right]\n",
    "            #如果最右数字不是偶数，则返回空\n",
    "            if counter[temp]>=1 and temp%2!=0:\n",
    "                return []\n",
    "            #如果右数字和其1/2数字依然在数组中\n",
    "            if counter[temp]>=1 and counter[temp//2]>=1:\n",
    "                res.append(temp//2)\n",
    "                counter[temp]-=1\n",
    "                counter[temp//2]-=1\n",
    "            #右数字还在，但其一半数字不在，返回空\n",
    "            elif counter[temp]>=1 and counter[temp//2]<1:\n",
    "                return []\n",
    "            #右指针左移\n",
    "            right-=1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort(reverse = True)\n",
    "        res = []\n",
    "        if len(changed) % 2 != 0: return res\n",
    "        \n",
    "        zeros = changed.count(0)\n",
    "        if zeros % 2 != 0: return res\n",
    "        else: res = res + [0] * (zeros // 2)\n",
    "            \n",
    "        ctr = collections.Counter(changed)\n",
    "        \n",
    "        for num in changed:\n",
    "            if num == 0: continue\n",
    "            if ctr[num] == 0: continue\n",
    "            if num % 2 != 0: continue\n",
    "            ctr[num] -= 1\n",
    "            if ctr.get(num // 2) is not None and ctr[num // 2] > 0:\n",
    "                #print(num)\n",
    "                res.append(num // 2)\n",
    "                ctr[num // 2] -= 1\n",
    "        \n",
    "        return res if len(res) == len(changed) // 2 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort(); hq = []; ans = [] #排序，优先匹配较小的\n",
    "        for i in range(len(changed)):\n",
    "            if hq and hq[0] * 2 == changed[i]: ans.append(heapq.heappop(hq)) # 匹配\n",
    "            else: heapq.heappush(hq, changed[i]) \n",
    "        return ans if not hq else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        length = len(changed)\n",
    "        if length % 2:\n",
    "            return []\n",
    "        count = collections.Counter(changed)\n",
    "        changed = list(count)\n",
    "        changed.sort()\n",
    "        original = []\n",
    "        if 0 in changed:\n",
    "            if count[0] % 2:\n",
    "                return []\n",
    "            else:\n",
    "                original += [0]*(count[0]//2)\n",
    "                changed.remove(0)\n",
    "        while changed:\n",
    "            num = changed.pop(0)\n",
    "            if count[num] <= count[num*2]:\n",
    "                original += [num] * count[num]\n",
    "                count[num*2] -= count[num]\n",
    "                if not count[num*2]:\n",
    "                    changed.remove(num*2)\n",
    "            else:\n",
    "                return []\n",
    "        return original\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        len_nums=len(changed)\n",
    "        if len_nums%2==1:return []\n",
    "        arr=[]\n",
    "        changed.sort()\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<len_nums:\n",
    "            if arr==[]:arr.append(changed[i])\n",
    "            elif arr[0]*2==changed[i]:\n",
    "                changed[j]=arr[0]\n",
    "                arr.pop(0)\n",
    "                j+=1\n",
    "            else:\n",
    "                arr.append(changed[i])\n",
    "            i+=1\n",
    "        if arr != []:return []\n",
    "        return changed[:j]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n % 2: return []\n",
    "        changed.sort()\n",
    "        l = 0\n",
    "        r = bisect_left(changed, 2 * changed[0])\n",
    "        if r == n or changed[r] != 2 * changed[0]: return []\n",
    "        if r == 0:\n",
    "            if changed[r + 1] != 0: return []\n",
    "            r += 1\n",
    "        ans = [changed[0]]\n",
    "        vis = [False] * n \n",
    "        vis[l] = vis[r] = True\n",
    "        while r < n:\n",
    "            while l < n and vis[l] == True:\n",
    "                l += 1\n",
    "            if l < n:\n",
    "                vis[l] = True\n",
    "            while r < n and (vis[r] == True or changed[r] < 2 * changed[l]):\n",
    "                r += 1\n",
    "            if r == n or changed[r] > 2 * changed[l]:\n",
    "                break\n",
    "\n",
    "            else:\n",
    "                ans.append(changed[l])\n",
    "                vis[r] = True \n",
    "        if len(ans) < n // 2: return []\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) & 1 or sum(changed) % 3:\n",
    "            return []\n",
    "\n",
    "        changed.sort()\n",
    "        res = []\n",
    "        q = deque()\n",
    "\n",
    "        for x in changed:\n",
    "            if q and q[0] << 1 == x:\n",
    "                res.append(q.popleft())\n",
    "            else:\n",
    "                q.append(x)\n",
    "\n",
    "        return [] if q else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) & 1 or sum(changed) % 3:\n",
    "            return []\n",
    "\n",
    "        changed.sort()\n",
    "\n",
    "        res, q = [], collections.deque()\n",
    "        # 排序后按顺序遍历，原值 x 与双倍值 y 一定\n",
    "        # 按顺序排列在一起，且 x 一定都在其 y 的前面\n",
    "        # 当遍历到原数组值的双倍，则将小的加入\n",
    "        # 否则预存小值等待双倍出现\n",
    "        for x in changed:\n",
    "            if q and q[0] * 2 == x:\n",
    "                res.append(q.popleft())\n",
    "            else:\n",
    "                q.append(x)\n",
    "        \n",
    "        # 最后若队列非空，表示有 x 找不到 y\n",
    "        return [] if q else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n % 2 != 0:\n",
    "            return []\n",
    "        changed.sort()\n",
    "        res = []\n",
    "        cnt = Counter()\n",
    "        for idx, val in enumerate(changed):\n",
    "            if cnt[val] == 0:\n",
    "                cnt[val * 2] += 1\n",
    "                res.append(val)\n",
    "            else:\n",
    "                cnt[val] -= 1\n",
    "                if cnt[val] == 0:\n",
    "                    del cnt[val]\n",
    "        if len(cnt) == 0:\n",
    "            return res \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        # 数组长度是奇数一定无解\n",
    "        if (n & 1) == 1:\n",
    "            return []\n",
    "        changed.sort()\n",
    "\n",
    "        res, q = [], collections.deque()\n",
    "        # 排序后按顺序遍历，原值 x 与双倍值 y 一定\n",
    "        # 按顺序排列在一起，且 x 一定都在其 y 的前面\n",
    "        # 当遍历到原数组值的双倍，则将小的加入\n",
    "        # 否则预存小值等待双倍出现\n",
    "        for x in changed:\n",
    "            if q and q[0] * 2 == x:\n",
    "                res.append(q.popleft())\n",
    "            else:\n",
    "                q.append(x)\n",
    "        \n",
    "        # 最后若队列非空，表示有 x 找不到 y\n",
    "        return [] if q else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        # changed = [1,3,4,2,6,8]\n",
    "        total = sum(changed)\n",
    "        if total % 3 != 0:\n",
    "            return []\n",
    "        \n",
    "        if len(changed) % 2 == 1:\n",
    "            return []\n",
    "        sl = SortedList([i for i in changed if i > 0])\n",
    "        if len(sl) % 2 == 1:\n",
    "            return []\n",
    "        zero = changed.count(0)\n",
    "        res = []\n",
    "        while sl:\n",
    "            first = sl[0]\n",
    "            second = sl[0] * 2\n",
    "            if first in sl and second in sl:\n",
    "                sl.remove(first)\n",
    "                sl.remove(second)\n",
    "                res.append(first)\n",
    "            else:\n",
    "                return []\n",
    "        return res if zero == 0 else res + [0] * ((zero) // 2)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        sorted_changed = sorted(changed)\n",
    "        if sorted_changed.count(0) % 2 != 0:\n",
    "            return []\n",
    "        cnt_changed = Counter(changed)\n",
    "        if cnt_changed[0] & cnt_changed[0] % 2 != 0:\n",
    "            return []\n",
    "        for i in sorted_changed:\n",
    "            if cnt_changed[i]:\n",
    "                cnt_changed[i] -= 1\n",
    "                if cnt_changed[2 * i]:\n",
    "                    result.append(i)\n",
    "                    cnt_changed[2*i] -= 1\n",
    "                else:\n",
    "                    return []\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n % 2 != 0:\n",
    "            return []\n",
    "        \n",
    "        numDict = collections.Counter(changed)\n",
    "        heapq.heapify(changed)\n",
    "        res = []\n",
    "        target = n//2\n",
    "        while len(res) < target:\n",
    "            n = heapq.heappop(changed)\n",
    "            if n not in numDict:\n",
    "                continue\n",
    "            if n*2 not in numDict:\n",
    "                return []\n",
    "            if n == 0 and numDict[n] < 2:\n",
    "                return []\n",
    "            res.append(n)\n",
    "            numDict[n] -= 1\n",
    "            if numDict[n] == 0: del numDict[n]\n",
    "            numDict[n*2] -= 1\n",
    "            if numDict[n*2] == 0: del numDict[n*2]\n",
    "             \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        to_remove = collections.Counter()\n",
    "        ans = []\n",
    "        changed.sort()\n",
    "        for num in changed:\n",
    "            if to_remove[num] == 0:\n",
    "                ans.append(num)\n",
    "                to_remove[num*2] += 1\n",
    "            else:\n",
    "                to_remove[num] -= 1\n",
    "        if len(ans) * 2 == len(changed):\n",
    "            return ans\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        c = Counter(changed)\n",
    "        if c[0] & 1: \n",
    "            return []\n",
    "        for x in sorted(c):\n",
    "            if c[x] > c[x << 1]: \n",
    "                return []\n",
    "            c[x << 1] -= c[x] if x else c[x] >> 1\n",
    "        return [*c.elements()]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed)%2!=0 or sum(changed)%3!=0:return []\n",
    "        d=Counter(changed)\n",
    "        res=[]\n",
    "        key=list(d.keys())\n",
    "        key.sort()\n",
    "        for i in key:\n",
    "            j=d[i]\n",
    "            if i==0:\n",
    "                if j%2!=0:return []\n",
    "                else:\n",
    "                    res+=[0]*(j//2)\n",
    "                continue\n",
    "            if j==0:continue\n",
    "            dou=i*2\n",
    "            if d[dou]<j:\n",
    "                return []\n",
    "            res+=[i]*j\n",
    "            d[dou]-=j\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) & 1 or sum(changed) % 3:\n",
    "            return []\n",
    "        c = Counter(changed)\n",
    "        ans = []\n",
    "        # 0特殊处理\n",
    "        if c[0] & 1:\n",
    "            return ans\n",
    "        ans.extend([0] * (c[0] >> 1))\n",
    "        del c[0]\n",
    "\n",
    "        for n in sorted(c):\n",
    "            if c[n << 1] < c[n]:\n",
    "                return []\n",
    "            ans.extend([n] * c[n])\n",
    "            c[n << 1] -= c[n]\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed)%2!=0 or sum(changed)%3!=0:return []\n",
    "        d=Counter(changed)\n",
    "        res=[]\n",
    "        key=list(d.keys())\n",
    "        key.sort()\n",
    "        for i in key:\n",
    "            j=d[i]\n",
    "            if i==0:\n",
    "                if j%2!=0:return []\n",
    "                else:\n",
    "                    res+=[0]*(j//2)\n",
    "                continue\n",
    "            if j==0:continue\n",
    "            dou=i*2\n",
    "            if d[dou]<j:\n",
    "                return []\n",
    "            res+=[i]*j\n",
    "            d[dou]-=j\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed)%2!=0 or sum(changed)%3!=0:return []\n",
    "        d=Counter(changed)\n",
    "        res=[]\n",
    "        key=list(d.keys())\n",
    "        key.sort()\n",
    "        for i in key:\n",
    "            j=d[i]\n",
    "            if i==0:\n",
    "                if j%2!=0:return []\n",
    "                else:\n",
    "                    res+=[0]*(j//2)\n",
    "                continue\n",
    "            if j==0:continue\n",
    "            dou=i*2\n",
    "            if d[dou]<j:\n",
    "                return []\n",
    "            res+=[i]*j\n",
    "            d[dou]-=j\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) & 1:\n",
    "            return []\n",
    "        deleted = deque()\n",
    "        changed.sort()\n",
    "        ans = []\n",
    "        for x in changed:\n",
    "            if deleted:\n",
    "                if deleted[0] == x:\n",
    "                    deleted.popleft()\n",
    "                    continue\n",
    "                if deleted[0] < x:\n",
    "                    break\n",
    "            ans.append(x)\n",
    "            deleted.append(2*x)\n",
    "        return [] if deleted else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(changed)\n",
    "        if n % 2:\n",
    "            return []\n",
    "\n",
    "        ans = []\n",
    "        cnt = Counter(changed)\n",
    "        for num in sorted(cnt):\n",
    "            if num == 0:\n",
    "                if cnt[num] % 2:\n",
    "                    return []\n",
    "                ans.extend([num] * (cnt[num] // 2))\n",
    "            else:\n",
    "                if cnt[num]:\n",
    "                    if cnt[num * 2] < cnt[num]:\n",
    "                        return []\n",
    "                    ans.extend([num] * cnt[num])\n",
    "                    cnt[num * 2] -= cnt[num]\n",
    "                \n",
    "        return ans if len(ans) == n // 2 else []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "      def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort()\n",
    "        n = len(changed)\n",
    "        if n % 2 == 1:\n",
    "            return []\n",
    "        r = []\n",
    "        dict={}\n",
    "        for i in range(len(changed)):\n",
    "            if changed[i] in dict.keys() and dict[changed[i]]>0:\n",
    "                if dict[changed[i]]==1:\n",
    "                    del(dict[changed[i]])\n",
    "                else:\n",
    "                    dict[changed[i]] -= 1\n",
    "                r.append(int(changed[i]/2))\n",
    "            # elif changed[i] in dict.keys() and dict[changed[i]]==0:\n",
    "            #     dict[changed[i]] = 1\n",
    "            #     # r.append(changed[i])\n",
    "            else:\n",
    "                tw=changed[i]*2\n",
    "                if tw in dict.keys():\n",
    "                    dict[tw]+=1\n",
    "                else:\n",
    "                    dict[tw]=1\n",
    "\n",
    "        if len(r)!=int(n / 2):r=[]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed)%2==1:\n",
    "            return []\n",
    "        changed.sort()\n",
    "        d = {}\n",
    "        for c in changed:\n",
    "            if c in d:\n",
    "                d[c] += 1\n",
    "            else:\n",
    "                d[c] = 1\n",
    "                \n",
    "        res = []\n",
    "        for c in changed:\n",
    "            if c in d:\n",
    "                d[c] -= 1\n",
    "                if d[c] == 0:\n",
    "                    d.pop(c)\n",
    "                if 2*c in d:\n",
    "                    res.append(c)\n",
    "                    d[2*c] -= 1\n",
    "                    if d[2*c] == 0:\n",
    "                        d.pop(2*c)\n",
    "        if len(res) == len(changed)//2:\n",
    "            return res\n",
    "        return []\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort()\n",
    "        res, cnts = [], collections.Counter(changed)\n",
    "        for x in changed:\n",
    "            if cnts[x] > 0:\n",
    "                # 注意只有当计数仍大于0的话才判断, 否则说明已经被作为一个2倍数字用掉了\n",
    "                if cnts[2 * x] <= 0 or x == 0 and cnts[x] < 2:\n",
    "                    # 如果二倍数字不存在, 或者当前数字是0且计数小于2, 肯定不可能是双倍数组\n",
    "                    return []\n",
    "                # x属于原数组\n",
    "                res.append(x)\n",
    "                cnts[x] -= 1\n",
    "                cnts[2 * x] -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "\n",
    "        if len(changed) & 1:\n",
    "            return []\n",
    "        \n",
    "        a = SortedList(changed)\n",
    "        while len(a):\n",
    "            x = a[0]\n",
    "            ans.append(x)\n",
    "            a.remove(x)\n",
    "            try:\n",
    "                a.remove(x*2)\n",
    "            except ValueError:\n",
    "                return []\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: list[int]) -> list[int]:        \n",
    "        b = []\n",
    "        changed_1 = sorted(changed)\n",
    "        new_changed = Counter(changed)\n",
    "        for i in changed_1:\n",
    "            if new_changed[i] == 0 :\n",
    "                continue\n",
    "            # if i*2 not in new_changed and i//2 not in new_changed:\n",
    "            #     return []\n",
    "            new_changed[i]=new_changed[i]-1\n",
    "            new_changed[i*2] = new_changed[i*2]-1\n",
    "            if new_changed[i*2]<0:\n",
    "                return []\n",
    "            b.append(i)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n % 2: return []\n",
    "        cnt = Counter(changed)\n",
    "        nums = [k for k in cnt.keys()]\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        if 0 in nums:\n",
    "            m = cnt[0]\n",
    "            if m % 2: return []\n",
    "            else: res = [0] * (m // 2)\n",
    "        for x in nums:\n",
    "            if x == 0: continue\n",
    "            if cnt[x] == 0: continue\n",
    "            if x * 2 not in cnt.keys():\n",
    "                return []\n",
    "            else:\n",
    "                if cnt[x * 2] < cnt[x]:\n",
    "                    return []\n",
    "                else:\n",
    "                    t = cnt[x]\n",
    "                    cnt[x * 2] -= t\n",
    "                    cnt[x] = 0\n",
    "                    for _ in range(t):\n",
    "                        res.append(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) % 2 != 0:\n",
    "            return []\n",
    "        \n",
    "        dic = collections.Counter(changed)\n",
    "        a = list(set(changed))\n",
    "        a.sort()\n",
    "        ans = []\n",
    "\n",
    "        for each in a:\n",
    "            if each == 0:\n",
    "                if dic[each] % 2 != 0:\n",
    "                    return []\n",
    "                else:\n",
    "                    ans.extend([0] * int(dic[each]/2))\n",
    "            elif dic[each]:\n",
    "                b = int(each*2)\n",
    "                if b not in dic:\n",
    "                    return []\n",
    "                else:\n",
    "                    if dic[b] < dic[each]:\n",
    "                        return []\n",
    "                    else:\n",
    "                        ans.extend([each] * dic[each])\n",
    "                        dic[b] -= dic[each]\n",
    "\n",
    "        if len(ans) == int(len(changed)/2):\n",
    "            return ans\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) & 1 or sum(changed)%3!=0:\n",
    "            return []\n",
    "        d=Counter(changed)\n",
    "        res=[]\n",
    "        for i in sorted(d):\n",
    "            j=d[i]\n",
    "            if i==0:\n",
    "                if j%2!=0:return []\n",
    "                else:\n",
    "                    res+=[0]*(j//2)\n",
    "                continue\n",
    "            if j==0:continue\n",
    "            dou=i*2\n",
    "            if d[dou]<j:\n",
    "                return []\n",
    "            res+=[i]*j\n",
    "            d[dou]-=j\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        # 排序 + 查找\n",
    "        # 1. 将原数组按从小到大排序\n",
    "        num = sorted(changed)\n",
    "        # 存奇数\n",
    "        list1 = {}\n",
    "        out = []\n",
    "        # 存偶数\n",
    "        list2 = {}\n",
    "        # 2. 开始遍历有序后的数组\n",
    "        for i in range(len(num)):\n",
    "            # 2.1. 如果是奇数\n",
    "            if num[i] % 2 != 0:\n",
    "                # 2.1.1. 奇数则一定是原数组内的元素，所以直接存入哈希表内\n",
    "                if num[i] not in list1:\n",
    "                    list1[num[i]] = 1\n",
    "                else:\n",
    "                    list1[num[i]] += 1\n",
    "            # 2.2. 如果是偶数\n",
    "            else:\n",
    "                # 2.2.1. 偶数则需要考虑其一半的元素在不在奇数哈希表内，\n",
    "                #        同时需要注意其一半的元素在奇数哈希表内的个数不能为0\n",
    "                #        为0则代表无法与该元素匹配\n",
    "                if num[i]//2 in list1 and list1[num[i]//2] != 0:\n",
    "                    # 2.2.1.1. 次数减一，表示匹配上一个，同时存入输出数组\n",
    "                    list1[num[i]//2] -= 1\n",
    "                    out.append(num[i]//2)\n",
    "                # 2.2.2. 去偶数哈希表内找有没有其一半的元素，\n",
    "                #        同样也需要判断个数是不是为0\n",
    "                elif num[i]//2 in list2 and list2[num[i]//2] != 0:\n",
    "                    # 2.2.2.1. 同样次数减一，存入输出数组\n",
    "                    list2[num[i]//2] -= 1\n",
    "                    out.append(num[i]//2)\n",
    "                # 2.2.3. 都没有找到，则表明该元素应当是原数组的元素，所以存入偶数哈希表\n",
    "                else:\n",
    "                    if num[i] not in list2:\n",
    "                        list2[num[i]] = 1\n",
    "                    else:\n",
    "                        list2[num[i]] += 1\n",
    "        # 3. 判断奇数和偶数哈希表所有元素是否为0\n",
    "        if (list1 and max(list1.values())!= 0) or (list2 and max(list2.values())!= 0) :\n",
    "            # 3.1. 不为0 则表示有未匹配的，所以返回空\n",
    "            return []\n",
    "        return out\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort()\n",
    "        cnt = Counter(changed)\n",
    "        ans = []\n",
    "        for num in changed:\n",
    "            if not cnt[num]:\n",
    "                continue\n",
    "            if num == 0:\n",
    "                if cnt[num] % 2:\n",
    "                    return []\n",
    "                ans.extend([0]*(cnt[num]//2))\n",
    "                cnt[num] = 0\n",
    "                continue\n",
    "            if cnt[2*num] < cnt[num]:\n",
    "                return []\n",
    "            ans.extend([num]*cnt[num])\n",
    "            cnt[2*num] -= cnt[num]\n",
    "            cnt[num] = 0\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        ans=[]\n",
    "        if len(changed)%2!=0:\n",
    "            return []\n",
    "        arr=[0]*(10**5+7)\n",
    "        for i in changed:\n",
    "            arr[i]+=1\n",
    "        if arr[0]%2!=0:\n",
    "            return []\n",
    "        ans+=[0]*(arr[0]//2)\n",
    "        arr[0]=0\n",
    "        print(arr[:10])\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]>0:\n",
    "                if i*2>10**5 or arr[i*2]<arr[i]:\n",
    "                    return []\n",
    "                else:\n",
    "                    ans+=[i]*arr[i]\n",
    "                    arr[i*2]-=arr[i]\n",
    "                    arr[i]=0\n",
    "            if i<10:\n",
    "                print(arr[:10])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n & 1:\n",
    "            return []\n",
    "        cnt = Counter(changed)\n",
    "        changed.sort(reverse=True)\n",
    "        res = []\n",
    "        for k in changed:\n",
    "            if len(res) == n // 2:\n",
    "                break\n",
    "            if cnt[k]:\n",
    "                cnt[k] -= 1\n",
    "                if not k & 1 and cnt.get(k // 2, 0):\n",
    "                    res.append(k // 2)\n",
    "                    cnt[k // 2] -= 1\n",
    "        return res if len(res) == n // 2 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n % 2 == 1:\n",
    "            return []\n",
    "        ans = []\n",
    "        sort = SortedList(changed)\n",
    "        while sort:\n",
    "            big = sort[-1]\n",
    "            if big % 2 == 1 or sort.count(big // 2) == 0:\n",
    "                return []\n",
    "            sort.remove(big)\n",
    "            sort.remove(big // 2)\n",
    "            ans.append(big // 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n=len(changed)\n",
    "        if n%2:return []\n",
    "\n",
    "        ans =[]\n",
    "        d=Counter(changed)\n",
    "        la=[(k,v) for k,v in d.items()]\n",
    "        la.sort(key =lambda x:x[0])\n",
    "        if 0 in d:\n",
    "            if d[0]%2==1:\n",
    "                return []\n",
    "            ans.extend([0]* (d[0]//2))\n",
    "\n",
    "        for x,_ in la:\n",
    "            if d[x]==0:\n",
    "                continue\n",
    "            elif (t:=x+x) not in d or  d[t]<d[x]:\n",
    "                return []\n",
    "            #del d[x]\n",
    "            d[t]-= d[x]\n",
    "            w=[x]*d[x]\n",
    "            \n",
    "            ans.extend(w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n % 2:\n",
    "            return []\n",
    "        changed.sort(reverse=True)\n",
    "\n",
    "        cnt = Counter(changed)\n",
    "\n",
    "        ans = []\n",
    "        for num in changed:\n",
    "            if num % 2 == 0:\n",
    "                if cnt[num] and cnt[num // 2]:\n",
    "                    ans.append(num//2)\n",
    "                    cnt[num] -= 1\n",
    "                    cnt[num // 2] -= 1\n",
    "        for key, val in cnt.items():\n",
    "            if val != 0:\n",
    "                return []\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort()\n",
    "        nums = {}\n",
    "        for num in changed:\n",
    "            nums[num] = nums.get(num,0)+1\n",
    "        #l 对0 特殊处理\n",
    "        res = []\n",
    "        visited = set()\n",
    "        if 0 in nums:\n",
    "            if nums[0]%2==1:\n",
    "                return []\n",
    "            else:\n",
    "                zeros = [0]*(nums[0]//2)\n",
    "                res=zeros\n",
    "                print(res)\n",
    "                del nums[0]\n",
    "                visited.add(0)\n",
    "                \n",
    "        \n",
    "        \n",
    "        for num in changed:\n",
    "            #l 要记得虽然字典删除了，但是changed没变\n",
    "            #但是又不能直接items遍历字典，因为字典长度一直在变\n",
    "\n",
    "            if num in visited and num not in nums:\n",
    "                continue\n",
    "            visited.add(num)\n",
    "\n",
    "            if num*2 in nums:\n",
    "                res.append(num)\n",
    "                if nums[num*2]>1:\n",
    "                    nums[num*2]-=1\n",
    "                    visited.add(num*2)\n",
    "                else: \n",
    "                    del nums[num*2]\n",
    "                    visited.add(num*2)\n",
    "\n",
    "                if nums[num]>1:#当num是0的时候，0的两倍是自己，字典里已经没有0了，就会报错\n",
    "                    nums[num]-=1\n",
    "                else: \n",
    "                    del nums[num]\n",
    "\n",
    "            else:\n",
    "                return []\n",
    "        if nums:\n",
    "            return []\n",
    "        else: \n",
    "            return res\n",
    "            #return changed[:len(changed)//2] #l 不能直接返回前一半"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort(reverse=True)\n",
    "        n = len(changed)\n",
    "        if n % 2 != 0:\n",
    "            return []\n",
    "        a = defaultdict(int)\n",
    "        b = []\n",
    "        for i in range(n):\n",
    "            if a[changed[i]*2] != 0:\n",
    "                b.append(changed[i])\n",
    "                a[changed[i]*2] -= 1\n",
    "            else:\n",
    "                a[changed[i]] += 1\n",
    "        if len(b) == n/2:\n",
    "            return b\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort(reverse=True)\n",
    "        n = len(changed)\n",
    "        if n % 2 != 0:\n",
    "            return []\n",
    "        a = defaultdict(int)\n",
    "        b = []\n",
    "        for i in range(n):\n",
    "            if a[changed[i]*2] != 0:\n",
    "                b.append(changed[i])\n",
    "                a[changed[i]*2] -= 1\n",
    "            else:\n",
    "                a[changed[i]] += 1\n",
    "        if len(b) == n/2:\n",
    "            return b\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        mapping = {}\n",
    "        for num in changed:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "        keys = sorted(mapping.keys())\n",
    "        result = []\n",
    "        delete = set()\n",
    "        for num in keys:\n",
    "            if(num in delete):\n",
    "                continue\n",
    "            if(num == 0):\n",
    "                if(mapping[0] % 2 == 1):\n",
    "                    return []\n",
    "                else:\n",
    "                    result += [0]*(mapping[0]//2)\n",
    "                \n",
    "            else:\n",
    "                if(2*num not in mapping or mapping[2*num] < mapping[num]):\n",
    "                    return []\n",
    "                result += [num]*mapping[num]\n",
    "                mapping[2*num] -= mapping[num]\n",
    "                if(mapping[2*num] == 0):\n",
    "                    del mapping[2*num]\n",
    "                    delete.add(2*num)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        num = [0] * 10**6\n",
    "        lis = []\n",
    "        changed.sort()\n",
    "        if len(changed) % 2:\n",
    "            return []\n",
    "        count = 0\n",
    "        for i in range(len(changed) - 1, -1, -1):\n",
    "            if changed[i] % 2 == 0:\n",
    "                if num[changed[i]] == 0: # 倍数\n",
    "                    num[changed[i] // 2] += 1\n",
    "                    count += 1\n",
    "                else:\n",
    "                    num[changed[i]] -= 1\n",
    "                    count -= 1\n",
    "                    lis.append(changed[i])\n",
    "            else:\n",
    "                if num[changed[i]] == 0:\n",
    "                    return []\n",
    "                else:\n",
    "                    num[changed[i]] -= 1\n",
    "                    count -= 1\n",
    "                    lis.append(changed[i])\n",
    "        if count == 0:\n",
    "            return lis\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        mapping = {}\n",
    "        for num in changed:\n",
    "            if(num not in mapping):\n",
    "                mapping[num] = 1\n",
    "            else:\n",
    "                mapping[num] += 1\n",
    "        keys = sorted(mapping.keys())\n",
    "        result = []\n",
    "        delete = set()\n",
    "        for num in keys:\n",
    "            if(num in delete):\n",
    "                continue\n",
    "            if(num == 0):\n",
    "                if(mapping[0] % 2 == 1):\n",
    "                    return []\n",
    "                else:\n",
    "                    result += [0]*(mapping[0]//2)\n",
    "            else:\n",
    "                if(2*num not in mapping or mapping[2*num] < mapping[num]):\n",
    "                    return []\n",
    "                result += [num]*mapping[num]\n",
    "                mapping[2*num] -= mapping[num]\n",
    "                if(mapping[2*num] == 0):\n",
    "                    del mapping[2*num]\n",
    "                    delete.add(2*num)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed)%2 != 0:\n",
    "            return []\n",
    "        changed.sort()\n",
    "        changed = [[i, False] for i in changed]\n",
    "        re_len = len(changed)//2\n",
    "        index_re = 0\n",
    "        re_list = []\n",
    "        index_re2 = 1\n",
    "        while index_re2 < len(changed):\n",
    "            if changed[index_re][0]*2 == changed[index_re2][0]:\n",
    "                re_list.append(changed[index_re][0])\n",
    "                changed[index_re][1] = True\n",
    "                changed[index_re2][1] = True\n",
    "                while index_re < len(changed) and changed[index_re][1]:\n",
    "                    index_re = index_re + 1\n",
    "                while index_re2 < len(changed) and (changed[index_re2][1] or index_re == index_re2): \n",
    "                    index_re2 = index_re2 + 1\n",
    "                \n",
    "            else:\n",
    "                index_re2 += 1\n",
    "        if len(re_list) != re_len:\n",
    "            return []\n",
    "        return re_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) % 2 != 0:  # edge case\n",
    "            return []\n",
    "        counter = Counter(changed)\n",
    "        res = []\n",
    "        if 0 in counter:\n",
    "            if counter[0] % 2 == 0:\n",
    "                res.extend([0] * (counter[0] // 2))\n",
    "                counter.pop(0)\n",
    "            else:\n",
    "                return []\n",
    "        arr = sorted([(num, freq) for num, freq in counter.items()])\n",
    "        while arr:\n",
    "            num, freq = arr.pop(0)\n",
    "            idx = bisect.bisect_left(arr, num * 2, key=lambda x: x[0])\n",
    "            if idx == len(arr) or arr[idx][0] != num * 2 or arr[idx][1] < freq:\n",
    "                return []\n",
    "            res.extend([num] * freq)\n",
    "            new_freq = arr[idx][1] - freq\n",
    "            if new_freq != 0:\n",
    "                arr[idx] = (num * 2, new_freq)\n",
    "            else:\n",
    "                arr.pop(idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed):\n",
    "        changed.sort()\n",
    "        res, cnts = [], collections.Counter(changed)\n",
    "        print(res)\n",
    "        print(cnts)\n",
    "        print(cnts[4])\n",
    "        for x in changed:\n",
    "            if cnts[x] > 0:\n",
    "                # 注意只有当计数仍大于0的话才判断, 否则说明已经被作为一个2倍数字用掉了\n",
    "                if cnts[2 * x] <= 0 or x == 0 and cnts[x] < 2:\n",
    "                    # 如果二倍数字不存在, 或者当前数字是0且计数小于2, 肯定不可能是双倍数组\n",
    "                    return []\n",
    "                # x属于原数组\n",
    "                res.append(x)\n",
    "\n",
    "                cnts[x] -= 1\n",
    "                cnts[2 * x] -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        #if len(changed) == 1: return []\n",
    "        from collections import Counter\n",
    "        count, res = Counter(changed), []\n",
    "\n",
    "        for k in sorted(count.keys()):\n",
    "            while count[k] > 0:\n",
    "                res.append(k)\n",
    "                count[k] -= 1\n",
    "                if count[2*k] == 0:\n",
    "                    return []\n",
    "                count[2*k] -= 1\n",
    "\n",
    "        print(res, count)\n",
    "        return res if sum(count.values()) == 0 else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed)%2!=0:return []\n",
    "        if sum(changed)%3!=0:return []\n",
    "        changed.sort()\n",
    "        d=Counter(changed)\n",
    "        res=[]\n",
    "        key=list(d.keys())\n",
    "        key.sort()\n",
    "        print(key,d)\n",
    "        for i in key:\n",
    "            j=d[i]\n",
    "            if i==0:\n",
    "                if j%2!=0:return []\n",
    "                else:\n",
    "                    res+=[0]*(j//2)\n",
    "                continue\n",
    "            if j==0:continue\n",
    "            dou=i*2\n",
    "            if d[dou]<j:\n",
    "                return []\n",
    "            res+=[i]*j\n",
    "            d[i]=0\n",
    "            d[dou]-=j\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        changedSize = 0\n",
    "        changedSet = collections.defaultdict(int)\n",
    "        nZero = 0\n",
    "        for n in changed:\n",
    "            if n > 0:\n",
    "                changedSet[n] += 1\n",
    "                changedSize += 1\n",
    "            else:\n",
    "                nZero += 1\n",
    "        \n",
    "        sortedChanged = sorted(changed)\n",
    "        for n in sortedChanged:\n",
    "            if changedSet[n] * changedSet[2 * n] > 0 and n > 0:\n",
    "                res.append(n)\n",
    "                changedSet[n] -= 1\n",
    "                changedSet[2 * n] -= 1\n",
    "        \n",
    "        return res + [0] * (nZero // 2) if sum([v for k, v in changedSet.items()]) == 0 and nZero % 2 == 0 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        result, ct = [], Counter(changed)\n",
    "        for i in range(max(ct)+1):\n",
    "            if not i:\n",
    "                if ct[i] & 1:\n",
    "                    return []\n",
    "                ct[i] >>= 1\n",
    "            if ct[i] > ct[i << 1]:\n",
    "                return []\n",
    "            result.extend([i] * ct[i])\n",
    "            ct[i<<1] -= ct[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        changed.sort()\n",
    "        records = defaultdict(int)\n",
    "        n = len(changed)\n",
    "        ans = []\n",
    "        for i in changed:\n",
    "            records[i] += 1\n",
    "        for j in changed:\n",
    "            double = 2*j\n",
    "            if double == 0:\n",
    "                records[double] -= 2\n",
    "                if records[double] >= 0:\n",
    "                    ans.append(j)\n",
    "                continue\n",
    "            if records[double] and records[j]:\n",
    "                records[double] -= 1\n",
    "                records[j] -= 1\n",
    "                if records[double] >= 0:\n",
    "                    ans.append(j)\n",
    "        print(ans)\n",
    "        return ans if len(ans) == n / 2 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        c = changed\n",
    "        c.sort()\n",
    "        res =[]\n",
    "        length = len(c)\n",
    "        if length % 2 != 0:\n",
    "            return []\n",
    "        count0 = c.count(0)\n",
    "        if count0 % 2 == 1:\n",
    "            return []\n",
    "        else:\n",
    "            if count0 > 0:\n",
    "                c = c[count0:]\n",
    "                res = [0] * (count0 // 2)\n",
    "        d = {}\n",
    "        for i , j in enumerate(c):\n",
    "            if j not in d:\n",
    "                d[j] = []\n",
    "                d[j].append(i)\n",
    "            else:\n",
    "                d[j].append(i)\n",
    "        for i , j in enumerate(c):\n",
    "            if j != '*':\n",
    "                tmp = j*2\n",
    "                if tmp in d:\n",
    "                    res.append(j)\n",
    "                    if d[tmp]:\n",
    "                        c[d[tmp][-1]] = '*'\n",
    "                        d[tmp].pop()\n",
    "                    else:\n",
    "                        del d[tmp]\n",
    "                else:\n",
    "                    return []\n",
    "        if len(res) == length / 2 :\n",
    "            return res \n",
    "        return []\n",
    "'''2007. 从双倍数组中还原原数组\n",
    "一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。\n",
    "给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。\n",
    "示例 1：\n",
    "输入：changed = [1,3,4,2,6,8]\n",
    "输出：[1,3,4]\n",
    "解释：一个可能的 original 数组为 [1,3,4] :\n",
    "- 将 1 乘以 2 ，得到 1 * 2 = 2 。\n",
    "- 将 3 乘以 2 ，得到 3 * 2 = 6 。\n",
    "- 将 4 乘以 2 ，得到 4 * 2 = 8 。\n",
    "其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。\n",
    "示例 2：\n",
    "输入：changed = [6,3,0,1]\n",
    "输出：[]\n",
    "解释：changed 不是一个双倍数组。\n",
    "示例 3：\n",
    "输入：changed = [1]\n",
    "输出：[]\n",
    "解释：changed 不是一个双倍数组。\n",
    "提示：\n",
    "1 <= changed.length <= 105\n",
    "0 <= changed[i] <= 105\n",
    "通过次数2,007提交次数7,294'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        c = changed\n",
    "        c.sort()\n",
    "        res =[]\n",
    "        length = len(c)\n",
    "        if length % 2 != 0:\n",
    "            return []\n",
    "        count0 = c.count(0)\n",
    "        if count0 % 2 == 1:\n",
    "            return []\n",
    "        else:\n",
    "            if count0 > 0:\n",
    "                c = c[count0:]\n",
    "                res = [0] * (count0 // 2)\n",
    "        d = {}\n",
    "        for i , j in enumerate(c):\n",
    "            if j not in d:\n",
    "                d[j] = []\n",
    "                d[j].append(i)\n",
    "            else:\n",
    "                d[j].append(i)\n",
    "        for i , j in enumerate(c):\n",
    "            if j != '*':\n",
    "                tmp = j*2\n",
    "                if tmp in d:\n",
    "                    res.append(j)\n",
    "                    if d[tmp]:\n",
    "                        c[d[tmp][-1]] = '*'\n",
    "                        d[tmp].pop()\n",
    "                    else:\n",
    "                        del d[tmp]\n",
    "                else:\n",
    "                    return []\n",
    "        if len(res) == length / 2 :\n",
    "            return res \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n & 1:\n",
    "            return []\n",
    "        count = Counter(changed)\n",
    "        # print(count)\n",
    "        items = list(count.items())\n",
    "        items.sort(key=lambda x:x[0])\n",
    "        count = {k:v for k, v in items}\n",
    "        # print(count)\n",
    "        ans = []\n",
    "        for k, v in count.items():\n",
    "            if k == 0:\n",
    "                if v & 1:\n",
    "                    return []\n",
    "                ans.extend([k]*(v//2))\n",
    "                continue\n",
    "            k2 = k*2\n",
    "            if v > 0: \n",
    "                if not k2 in count.keys() or count[k2] < v:\n",
    "                    return[]\n",
    "                ans.extend([k]*v)\n",
    "                count[k2] -= v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        counter = sorted(Counter(changed).items(), key=lambda kv: kv[0])\n",
    "        counter = dict(counter)\n",
    "        original = []\n",
    "        if 0 in counter:\n",
    "            if counter[0] % 2 == 1:\n",
    "                return []\n",
    "            else:\n",
    "                original.extend([0] * (counter[0] // 2))\n",
    "                del counter[0]\n",
    "        for elem, cnt in counter.items():\n",
    "            if cnt < 0:\n",
    "                return []\n",
    "            if cnt > 0:\n",
    "                elem2 = 2 * elem\n",
    "                if elem2 in counter and counter[elem2] > 0:\n",
    "                    original.extend([elem] * cnt)\n",
    "                    counter[elem2] -= cnt\n",
    "                else:\n",
    "                    return []\n",
    "        return original"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n=len(changed)\n",
    "        changed.sort()\n",
    "        print(changed)\n",
    "        if n%2==1:\n",
    "            print(\"fail 1\")\n",
    "            return []\n",
    "        counter=collections.Counter(changed)\n",
    "        print(counter)\n",
    "        res=[]\n",
    "        left=0\n",
    "        right=n-1\n",
    "\n",
    "        while left<right:\n",
    "            temp=changed[left]\n",
    "            if counter[temp]>=1 and counter[2*temp]>=1:\n",
    "                res.append(temp)\n",
    "                counter[temp]-=1\n",
    "                counter[2*temp]-=1\n",
    "            elif counter[temp]>=1 and counter[2*temp]<1:\n",
    "                print(\"fail 2\")\n",
    "                return []\n",
    "            left+=1\n",
    "\n",
    "            temp=changed[right]\n",
    "            if counter[temp]>=1 and temp%2!=0:\n",
    "                return []\n",
    "            if counter[temp]>=1 and counter[temp//2]>=1:\n",
    "                res.append(temp//2)\n",
    "                counter[temp]-=1\n",
    "                counter[temp//2]-=1\n",
    "            elif counter[temp]>=1 and counter[temp//2]<1:\n",
    "                print(\"fail 3\")\n",
    "                return []\n",
    "            \n",
    "            right-=1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in changed:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        lis = []\n",
    "        for i in dic:\n",
    "            lis.append([i, dic[i]])\n",
    "        lis.sort(key=lambda x:x[0])\n",
    "        locdic = {}\n",
    "        res = []\n",
    "        for i in range(len(lis)):\n",
    "            locdic[lis[i][0]] = i\n",
    "        #print(lis)\n",
    "        for i in range(len(lis)):\n",
    "            if lis[i][1] == 0:\n",
    "                continue\n",
    "            if lis[i][0] * 2 not in locdic:\n",
    "                return []\n",
    "            if lis[i][0] * 2 == lis[i][0]:\n",
    "                if lis[i][1] % 2 == 0:\n",
    "                    for k in range(lis[i][1] // 2):\n",
    "                        res.append(lis[i][0])\n",
    "                else:\n",
    "                    return []\n",
    "            else:\n",
    "                if lis[locdic[lis[i][0] * 2]][1] < lis[i][1]:\n",
    "                    return []\n",
    "                for k in range(lis[i][1]):\n",
    "                    res.append(lis[i][0])\n",
    "                lis[locdic[lis[i][0] * 2]][1] -= lis[i][1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        n = len(changed)\n",
    "        if n % 2:\n",
    "            return []\n",
    "        ans = []\n",
    "        changed.sort()\n",
    "        cnt = Counter(changed)\n",
    "        for num in changed:\n",
    "            if cnt[num]:\n",
    "                ans.append(num)\n",
    "                cnt[num] -= 1\n",
    "                cnt[num * 2] -= 1\n",
    "\n",
    "        return ans if len(ans) == n // 2 else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) % 2 == 1:\n",
    "            return []\n",
    "                \n",
    "        pos = defaultdict(list)\n",
    "        \n",
    "        changed.sort()\n",
    "        \n",
    "        for i,c in enumerate(changed):\n",
    "            pos[c].append(i)\n",
    "        \n",
    "        def judge(c):\n",
    "            if c not in pos or pos[c] == []:\n",
    "                return -1\n",
    "            p = pos[c][0]\n",
    "            pos[c].pop(-1)\n",
    "            return p\n",
    "            \n",
    "        ret = []\n",
    "        \n",
    "        for i,c in enumerate(changed):\n",
    "            if pos[c]== []:\n",
    "                continue\n",
    "            \n",
    "            pos[c].pop(-1)\n",
    "            p = judge(c*2)\n",
    "            \n",
    "            if p < 0:\n",
    "                return []\n",
    "            else:\n",
    "                ret.append(c)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if not changed or len(changed)%2!=0:\n",
    "            return []\n",
    "        ans=[]\n",
    "        num_dict=defaultdict(int)\n",
    "        changed.sort()\n",
    "        for num in changed:\n",
    "            num_dict[num]+=1\n",
    "        for num in changed:\n",
    "            if num_dict[num]>0 and num_dict[2*num]>0:\n",
    "                if num!=0:\n",
    "                    num_dict[num]-=1\n",
    "                    num_dict[2*num]-=1\n",
    "                    ans.append(num)\n",
    "                else:\n",
    "                    if num_dict[0]>=2:\n",
    "                        num_dict[0]-=2\n",
    "                        ans.append(0)\n",
    "                    else:\n",
    "                        return []\n",
    "        if len(ans)==len(changed)//2:\n",
    "            return ans\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOriginalArray(self, changed: List[int]) -> List[int]:\n",
    "        if len(changed) % 2 == 1:   return []\n",
    "        changed.sort(reverse = True)\n",
    "        numDict = collections.defaultdict(int)\n",
    "\n",
    "        ans = []\n",
    "        unmatch = 0\n",
    "        for num in changed:\n",
    "            if numDict[num * 2] == 0:\n",
    "                if numDict[num] == 0:   unmatch += 1\n",
    "                numDict[num] += 1\n",
    "            else:\n",
    "                ans.append(num)\n",
    "                numDict[num * 2] -= 1\n",
    "                if numDict[2*num] == 0:   unmatch -= 1\n",
    "        return ans if unmatch == 0 else []"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
